/*******************************************************************************
 * Copyright 2010 DemandSpot
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 ******************************************************************************/
package com.demandspot.utils.searchtree;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;

public class SearchTree<T extends SearchTreeElement> implements Serializable{
    protected TreeMap<String, SearchTreeNode<T>> tree;
    protected SearchTree<T> parent;
    private SearchTreeBuilder<T> builder = new SearchTreeBuilder<T>();
	private Comparator<T> sameElementsComparator;
	private int maxTreeLevels;

	SearchTree() {
		tree = new TreeMap<String, SearchTreeNode<T>>();
	}
    
    public SearchTree(List<T> allData, Comparator<T> sameElementsComparator, int maxTreeLevels) {
    	this();    	
    	this.sameElementsComparator = sameElementsComparator;
    	this.maxTreeLevels = maxTreeLevels;
    	builder.buildSearchTree(this, allData, sameElementsComparator, maxTreeLevels);
	}

	/**
	 * Build a search tree that uses its elements' natural ordering for same-element comparisons
	 */
    public SearchTree(List<T> allData, int maxTreeLevels) {
    	this();
    	this.sameElementsComparator = null;
    	this.maxTreeLevels = maxTreeLevels;
    	builder.buildSearchTree(this, allData, sameElementsComparator, maxTreeLevels);
	}

    public void addElement(T element) {
    	builder.addNode(sameElementsComparator, this, element, maxTreeLevels);
    }

	protected void addTreeNode(SearchTreeNode<T> node) {
        tree.put(node.key, node);
    }
    
    protected SearchTreeNode<T> getTreeNode(String nodeKey) {
        return tree.get(nodeKey);
    }
    
    /**
     * Get T elements for a given key
     * 
     * @param key prefix
     * @param maxResluts max elements to return
     * @return
     */
    public List<T> getValueByKey(String key, int maxResluts) {
        SearchTree<T> aTree = this;
        SearchTreeNode<T> node = null;
        key = key.toLowerCase();
        
        //did we find a node that matched the current key node 
        boolean fullKeyWasFound = false;
        
        for ( int i=0; i < key.length(); i++ ) {
        	fullKeyWasFound = false;
            String keyNode = key.substring(i, i+1);
            SearchTreeNode<T> _node = aTree.getTreeNode(keyNode);
            
            if ( _node != null ) {
                aTree = _node.tree;
                node = _node;
            } else {
                break;
            }
            fullKeyWasFound = true;
        }
        
        //node will be null when we don't have elements that starts or share common chars with the given key
        if (node != null) {
        	//we found nodes for all given key chars
            if (fullKeyWasFound)
                return node.getResultList(maxResluts);
            else 
            	//we didn't find nodes for all given key chars (not enough tree levels)
                return node.getResultList(key, maxResluts);
        }
        //default return
        return new ArrayList<T>();
    }
    
    protected SearchTreeNode<T> getLastMatchingTreeNode(String key) {
        SearchTree<T> aTree = this;
        SearchTreeNode<T> node = null;
        
        for ( int i=0; i < key.length(); i++ ) {
            String keyNode = key.substring(i, i+1);
            SearchTreeNode<T> _node = aTree.getTreeNode(keyNode);
            
            if ( _node != null ) {
                aTree = _node.tree;
                node = _node;
            } else {
                break;
            }
        }
        return node;
    }
    
    protected SearchTreeNode<T> getMatchingTreeNode(String key) {
        SearchTree<T> aTree = this;
        SearchTreeNode<T> node = null;
        
        for ( int i=0; i < key.length(); i++ ) {
            String keyNode = key.substring(i, i+1);
            node = aTree.getTreeNode(keyNode);
            
            if ( node != null ) {
                aTree = node.tree;
            } else {
                break;
            }
        }
        return node;
    }

    public void setParent(SearchTree<T> parent) {
        this.parent = parent;
    }

    public SearchTree<T> getParent() {
        return parent;
    }

	public void removeElement(T element) {
		SearchTree<T> aTree = this;
		SearchTreeNode<T> node = null;
		
		String[] keys = element.getKeys();
		
		for (String elementKey : keys) {
			for(int i=0; i < elementKey.length(); i++) {
				String keyNode = elementKey.substring(i, i+1);
	            node = aTree.getTreeNode(keyNode);
	            
	            if ( node != null ) {
	                aTree = node.tree;
	                node.elements.remove(element);
	            } else {
	                break;
	            }
			}
		}
	}
}
